The first Ethernet LAN (xe2x80x9cLocal Area Networkxe2x80x9d) was implemented on a shared medium, such as a single co-axial cable connecting all devices in the LAN. The shared medium imposed a signal length restriction on the physical medium and a limit to the number of devices that could be connected to the LAN because only one device could transmit data at a time on the shared medium.
A switch provides a means of increasing the size of a LAN by providing a bridge between groups of devices connected on the same physical medium or LAN segment. The LAN can be viewed as multiple LAN segments connected together by one or more switches. For example, if a first port in the switch is connected to a first LAN segment and a second port in the switch is connected to a second LAN segment. The switch acts as a bridge between the LAN segments by forwarding data packets destined for a device connected to the second LAN segment from the first LAN segment.
Each device connected to the LAN segment in the LAN is assigned a unique Media Access Control (xe2x80x9cMACxe2x80x9d) address. Each data packet includes a MAC source address assigned to the device transmitting the data packet and the MAC destination address of the device to which the data packet is to be forwarded.
The switch determines whether a data packet received on one LAN segment is to be forwarded on another LAN segment by associating a destination MAC address with a port in the switch; that port is connected to the LAN segment on which the MAC address resides. This association may be stored in a static forwarding entry in a forwarding table in the switch. A static forwarding entry is explicitly configured by management action and is not modified during the operation of the switch. For example, if device A is connected to LAN segment A and LAN segment A is connected to port 1 in the switch, a static forwarding entry for device A associates the MAC address for device A with port 1. If device A is physically moved to segment B connected to port 2 in the switch, the static entry in the forwarding table for device A is not automatically updated to forward to port 2 instead of port 1. A reconfiguration of the switch by management action is required to update a static forwarding entry.
The association between a MAC address and a port in the switch can be learned during operation of the switch instead of being explicitly configured in a static forwarding entry in the switch. Learning allows associations between MAC addresses and ports in the switch to be dynamically created and modified during operation of the switch. A learned association is stored in a dynamic forwarding entry in the forwarding table in the switch. In order to learn MAC addresses, the switch listens to data packets transmitted on all LAN segments connected to ports in the switch. The dynamic entry associates the MAC address with the port connected to the LAN segment from which a data packet is sourced.
The switch creates a new dynamic forwarding entry in the forwarding table upon detecting a MAC address stored in the source address field included in a data packet which does not have a corresponding forwarding entry in the forwarding table. The switch updates a dynamic forwarding entry associated with a MAC address each time it receives a data packet sourced from the MAC address.
For example, if the switch sees a data packet on segment A connected to port 1 with MAC address A stored in the source address field, the switch creates a dynamic forwarding entry in the forwarding table for MAC address A. The dynamic forwarding entry associates MAC address A with port 1. Subsequent data packets received from another port in the switch including MAC address A as the destination address are forwarded through port 1. If the device with MAC address A is moved to another LAN segment connected to port 2 in the switch, the switch learns the new association upon receiving a data packet on port 2 from MAC address A. The switch updates the dynamic forwarding entry for MAC address A to forward data packets to MAC address A through port 2 instead of port 1.
Increasing the size of a LAN, by providing multiple LAN segments through the use of a switch, increases the bandwidth of the LAN and thus the number of devices that can be connected to the LAN. However, by increasing the number of devices connected to the LAN, the bandwidth consumed by broadcast traffic also increases. Broadcast traffic increases because upon receiving a data packet for an unknown MAC address, a broadcast packet is forwarded to all devices connected to the LAN in order to learn forwarding information for the unknown MAC address. The broadcast data packet includes a special MAC address sourced by one MAC address, which is forwarded to all other devices connected to the LAN. Unlike unicast traffic; that is, a data packet which is transmitted from a single source address to a single destination address, broadcast traffic cannot be limited to a single LAN segment. Thus, as the number of devices connected to a LAN increases, the amount of broadcast traffic increases, reducing the available bandwidth on the LAN regardless of the number of physical LAN segments in the LAN.
A solution for reducing broadcast traffic in a LAN is provided by logically segmenting the LAN into Virtual Local Area Networks (xe2x80x9cVLANxe2x80x9d). A method for logically segmenting a LAN into VLANs is described in the Institute of Electric and Electronic Engineers (xe2x80x9cIEEExe2x80x9d) P802.1Q standard. In a switch supporting VLANS a broadcast data packet is only forwarded through a port if the port is a member of same VLAN from which the data packet was received. Thus, broadcast traffic is only forwarded to devices which are members of the same VLAN on which the broadcast data packet was sourced.
In a LAN logically segmented into VLANs, each data packet forwarded on the LAN includes a VLAN Identifier (xe2x80x9cVIDxe2x80x9d) identifying the VLAN from which the data packet was sourced. Membership of a VLAN is based on an assigned logical address, the VID, rather than a physical address. Thus, members of a VLAN need not be members of the same physical LAN segment. All traffic on the LAN, including broadcast, unicast and Multicast data traffic is restricted to the virtual VLAN on which it is sourced, by limiting the forwarding of traffic to members of the VLAN identified by the VID included in the data packet. A device can only communicate with a member of a VLAN if the device is also a member of the VLAN identified by the VID included in the received data packet. Thus, a VLAN contains broadcast traffic within the VLAN in which the broadcast packet is sourced and provides security for data transfer between members of the VLAN.
By applying VLANs to a LAN, a forwarding decision stored in a static forwarding entry or a dynamic forward entry is dependent on both the VID and the MAC address included in the received data packet. A MAC address may be a member of more than one VLAN requiring either a static or dynamic forwarding entry in the forward table for each VLAN in which the MAC address is a member. If the switch implements independent learning, a plurality of dynamic forwarding entries are provided for a MAC address, one for each VLAN in which the MAC address is learned.
In order to reduce the number of dynamic forwarding entries stored and updated for each learned MAC address, the switch may implement shared learning. Shared learning allows forwarding information learned for a MAC address on one VLAN to be shared by other VLANs in a given set of VLANs. The forwarding information is used for forwarding decisions taken for that MAC address.
To implement shared learning in a switch, each VLAN in the switch is associated with exactly one Filter Identifier (xe2x80x9cFIDxe2x80x9d). For independent learning there is a one-to one correspondence between a VID and a FID. For shared learning, a plurality of VIDs are assigned to a FID. Only the VID is forwarded in a data packet, the FID is randomly assigned by the switch and used internally in the switch. In a shared learning switch all learned information for independent learning or shared learning is stored in a dynamic forwarding entry in the forwarding table associated with a FID instead of a VID. Explicitly configured forwarding information is stored in a static forwarding entry associated with a VID. A switch may simultaneously support both shared learning and independent learning.
Shared VLAN learning allows learned MAC address information to be shared amongst a set of VLANs because only one dynamic forwarding entry associated with a FID is stored in the forwarding table for the FID. However, even though the MAC address forwarding information is shared amongst the set of VLANs in the FID, the switch only forwards a data packet through a port that is a member of the VLAN from which the data packet was sourced. This forwarding decision can be made through the use of egress filtering. Thus, in a shared learning switch, broadcast traffic is restricted to the VLAN from which it is sourced and security is provided between VLANs.
FIG. 1A illustrates a prior art forwarding table 130 implemented in a shared learning switch. The prior art forwarding table 130 includes static forwarding entries 130 and dynamic forwarding entries. The static forwarding entry 132 associates a forward vector 140 with a MAC address 136b and a VID 138. The dynamic entry 134 associates a forward vector 140 with a MAC address 136a and a FID 142. The forward vector 140a, 140b is a bit map including a bit for each port in the switch indicating the port or ports through which the data packet is to be forwarded. The VID 138 in the static forwarding entry 132 is the same VID included in the data packet received by the switch. The FID 142 stored in the dynamic forwarding entry 134 is associated with set of VIDs or a single VID. A forwarding entry associated with the MAC address and the VID included in a received data packet may be stored in a static forwarding entry 132 or a dynamic forwarding entry 134 dependent on whether the MAC address was learned by the switch or explicitly defined by management. Thus, two searches of the forwarding table 130 are required to determine a forwarding decision for a forwarding entry associated with a MAC address and VID included in a received data packet.
The first search searches for a static forwarding entry 132 dependent on the VID 138 included in the data packet, or a default VID. A default VID is assigned to the data packet dependent on the port at which the data packet was received if a VID is not included in the data packet. If there is no static forwarding entry 132 in the forwarding table 130 associated with the MAC address, a second search is performed for a dynamic forwarding entry 134 including the FID 142 assigned to the VID 138 by the switch and the MAC address 136a. 
Multiple searches of a filtering database increase the time for filtering a data packet received by a switch. We present a switch including a translator and a filtering database which performs a single search. The translator provides a translated identifier for an identifier associated with a data packet received by the switch. The translated identifier includes a group identifier corresponding to a virtual LAN group (FID) and a group member number corresponding to an identified virtual LAN (VID). The filter data base stores a static entry and a dynamic entry. The static entry stores a forwarding decision for the data packet associated with the translated identifier. The dynamic entry stores a forwarding decision for the data packet associated with the group identifier included in the translated identifier and the group member number set to don""t care. The translated identifier allows a filtering database to provide the forwarding decision stored in the static entry or the dynamic entry for the identifier from a single search operation.
The group identifier included in the translated identifier is stored in both the static entry and the dynamic entry. In the dynamic entry the group member number is set to don""t care. Thus, a single search operation can be used to find a match for the identifier which can be stored in either the static entry or the dynamic entry in the filtering database.
In certain embodiments, the group member number identifies one of several members associated with the group identifier. The filtering database may be a Content Addressable Memory. The Content Addressable Memory may be a ternary Content Addressable Memory for supporting a don""t care condition.
The identifier may be stored in a header included in the received data packet or a default identifier assigned to the received data packet by the switch.